/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include<bits/stdc++.h>  // 万能头文件
#include <vector> 
#include <string>
#include <cstring>  // atoi()【需要将string 用 c_str()函数转换】--stoi()函数--用于字符串转整数
#include <list>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>  // greater less等
#include <iterator>
#include<numeric>  // 用于对vector求和----accumulate函数
// #define NDEBUG
#include <assert.h>
using namespace boost;   // 支持string的操作
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<T>& arr, string const str){
    cout << str << ": ";
    // typename T::const_iterator it = arr.begin();
    for(auto it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
typedef struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}TreeNode,*TreeLink;

// 模拟所说的
class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    struct Node
    {
        int key;
        int val;
        Node(int k = 0, int v = 0) : key(k), val(v) {}
    };
    list<Node> m_list;  // 存储实际的内容
    unordered_map<int, list<Node>::iterator> m_map; // key为Node中的key，value就存储在链表中的位置---迭代器
    int m_maxListNum = 0;
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> ans;
        this->m_maxListNum = k;
        // write code here
        if (operators.size() == 0) return ans;
        for(auto& op : operators) {
            if (op[0]==1) {
                this->set(op[1],op[2]);
            } else if (op[0]==2) {
                ans.push_back(this->get(op[1]));
            }
        }
        return ans;
    }

    // 为了添加数据，额外加的
    void add(int key, int val) {
        // 不存在了
        int cnt = m_list.size();
        if (cnt >= m_maxListNum) {
            // 先删除最后的，然后插入队头
            auto last = m_list.end();
            remove(--last);  // 注意！！这是减减才行！！
        }
        m_list.push_front(Node(key, val));
        m_map[key] = m_list.begin();
    }

    void remove(list<Node>::iterator it) {
        int key = it->key;
        int val = it->val;
        m_map.erase(key);
        m_list.erase(it);
    }

    void set(int key, int val){
        
        // 假如已经存在--先删除再加
        auto it = m_map.find(key);
        if (it != m_map.end()) {
            // 删除
            remove(it->second);
        }
        add(key,val);
        return;
    }

    int get(int key){
        int val = -1;
        if (m_map.find(key) == m_map.end())
            return -1;
        
        // 有
        auto list_it = m_map[key];
        // 先记录
        val = list_it->val;
        // 更新列表
        remove(list_it);
        add(key, val);      

        return val;
    }
};

int main(int argc, const char** argv) {
    Solution solu = Solution();
    // 常见边界值
    // cout << INT32_MAX << endl;
    // cout << INT32_MIN << endl;
    // cout << INT_MAX << endl;
    // cout << INT_MIN << endl;
    int target = 7;
    vector<int> nums = {2,3,1,2,4,3};
    time_t start = time(NULL);
    cout << "start time is " << start << endl;

    // cout << solu.minSubArrayLen(target, nums) << endl;
    
    time_t end = time(NULL);
    cout << "end time is " << start << endl;
    cout << "耗时：" << end*100-start*100 << " s." <<endl;


    return 0;
}